package com.heima.leetcode.practice;

/**
 * leetcode 395. 至少有 K 个重复字符的最长子串
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/14 10:35
 */
public class E395 {
    /*
      分析：
      字符串1： aaabb  k=3 => aaa
      字符串2： ababbc  k=2 => ababb
      字符串3： aaaxbbcccxddddbdddefffef  k=3
               => aaa bbccc ddddbddd fff f
               => aaa ccc   dddd ddd fff
               => dddd
       所以思路就是在字符串中找到总出现数小于k的元素，将其排除，因为谁带它谁倒霉
       剩下分成了字串，再对各个字串进行递归处理，递归结束条件：当前字串的长度小于k
       、当前字符串没有出现小于k的字符，剩下的这些里面挑一个长度最长的字符串返回
     */

    /**
     * 找出字符串中最长的子串，要求子串中至少有k个重复字符
     * @param s 待处理的字符串
     * @param k 最少重复次数
     * @return 最长的子串的长度
     */
    public int longestSubstring(String s, int k) {
        // 1、递归结束条件：当前字符串的长度小于k
        if (s.length() < k){
            return 0;
        }
        // 2、统计字符串中每个字符出现的次数
        int[] count = new int[26];
        char[] charArray = s.toCharArray();
        for (char c : charArray) {
            count[c - 'a']++;
        }
        // 3、找出字符串中至出现次数少于k的字符，并将字符串切分，递归处理
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            int cnt = count[c - 'a'];
            if (cnt > 0 && cnt < k) {
                // i找到的是开始（包含），j找到的是结束（不包含），例如bbccc，i=0，j=2
                int j = i + 1;
                while (j < charArray.length && count[charArray[j] - 'a'] < k){
                    j++;
                }
                String substring1 = s.substring(0, i);
                String substring2 = s.substring(j, charArray.length);
                return Math.max(longestSubstring(substring1, k), longestSubstring(substring2, k));
            }
        }
        // 4、如果字符串中没有出现次数少于k的字符，则返回整个字符串的长度
        return charArray.length;
    }
}
